package com.cande.loki.exercise.algorithm;

/**
 * @Description 数组中连续数字的最小值
 * @Author wgf
 * @Date 2025/10/18 5:55 PM
 */
public class DP_AarrayMinSum {
    public static void main(String[] args) {
        int [] arr = {2,3,-1,-4,-1,5};
        int result = findMin(arr);
        System.out.println(result);

        System.out.println("_______");
        System.out.println(findMinDP(arr));
        int [] arr1 = {2,3,1,5};
        System.out.println(findMin(arr1));
        System.out.println(findMinDP(arr1));
    }

    /**
     * dp
     * @param arr
     * @return
     */
    private static int findMinDP(int[] arr) {
        int min = arr[0];
        int tempMin = arr[0];
        for (int i = 1; i < arr.length; i++) {
            tempMin = Math.min(arr[i], tempMin+arr[i] );
            min = Math.min(min,tempMin);
        }
        return min;
    }
    /**
     * 暴力解
     * @param arr
     * @return
     */
    private static int findMin(int[] arr) {
        int min = Integer.MAX_VALUE;


        for (int i = 0; i < arr.length; i++) {
            int temp = 0;
            for (int j = i; j < arr.length; j++) {
                temp += arr[j];
                if (temp < min){
                    min = temp;
                }
            }
        }
        return min;
    }
}
